Solution: Find The Duplicate Number

Let's solve the Find The Duplicate Number problem using the the Fast and Slow pattern.

Statement#

Given an unsorted array of positive numbers, nums, such that the values lie in the range [1,n][1, n], inclusive, and that there are n+1n+1 numbers in the array, find and return the duplicate number present in nums. There is only one repeated number in nums.

Note: You cannot modify the given array nums. You have to solve the problem using only constant extra space.

Constraints:

  • 1n1051 \leq n \leq 10^5
  • nums.length =n+1= n + 1
  • 11 \leq nums[i] n\leq n
  • All the integers in nums are unique except for one integer that will appear more than once.

Solution#

We solve this problem using fast and slow pointers technique, without modifying the nums array and using only constant extra space.

For this problem, the duplicate number will create a cycle in the nums array. The cycle in the nums array helps identify the duplicate number.

To find the cycle, we’ll move in the nums array using the f(x)=nums[x]f(x) = nums[x] function, where xx is the index of the array. This function constructs the following sequence to move:

x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ...x, \space nums[x], \space nums[nums[x]], \space nums[nums[nums[x]]], \space ...

In the sequence above, every new element is an element in nums present at the index of the previous element.

Let’s say we have an array, [2, 3, 1, 3][2, \space 3,\space 1,\space 3]. We’ll start with x=nums[0]x=nums[0], which is 22, present at the 0th0^{th} index of the array and then move to nums[x]nums[x], which is 11, present at the 2nd2^{nd} index. Since we found 11 at the 2nd2^{nd} index, we’ll move to the 1st1^{st} index, and so on. This example shows that if we’re given an array of length n+1n+1, with values in the range [1, n][1,\space n], we can use this traversal technique to visit all the locations in the array.

The following example illustrates this traversal:

Created with Fabric.js 3.6.6 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 Here, we have an array, nums.

1 of 11

Created with Fabric.js 3.6.6 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We found 2 at nums[0].nums[0] = 2 Let's start traversing in an array starting from 0 index.

2 of 11

Created with Fabric.js 3.6.6 We found 8 at nums[2].nums[0] = 2nums[2] = nums[nums[0]] = 8 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 2, since we found 2 at nums[0].

3 of 11

Created with Fabric.js 3.6.6 We found 1 at nums[8].nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 8, since we found 8 at nums[2].

4 of 11

Created with Fabric.js 3.6.6 We found 5 at nums[1]nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 1, since we found 1 at nums[8].

5 of 11

Created with Fabric.js 3.6.6 We found 3 at nums[5].nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5nums[5] = nums[nums[1]] = 3 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 5, since we found 5 at nums[1].

6 of 11

Created with Fabric.js 3.6.6 We found 6 at nums[3].nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5nums[5] = nums[nums[1]] = 3nums[3] = nums[nums[5]] = 6 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 3, since we found 3 at nums[5].

7 of 11

Created with Fabric.js 3.6.6 We found 9 at nums[6].nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5nums[5] = nums[nums[1]] = 3nums[3] = nums[nums[5]] = 6nums[6] = nums[nums[3]] = 9 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 6, since we found 6 at nums[3].

8 of 11

Created with Fabric.js 3.6.6 We found 7 at nums[9].nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5nums[5] = nums[nums[1]] = 3nums[3] = nums[nums[5]] = 6nums[6] = nums[nums[3]] = 9nums[9] = nums[nums[6]] = 7 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 9, since we found 9 at nums[6].

9 of 11

Created with Fabric.js 3.6.6 We found 8 at nums[7].nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5nums[5] = nums[nums[1]] = 3nums[3] = nums[nums[5]] = 6nums[6] = nums[nums[3]] = 9nums[9] = nums[nums[6]] = 7nums[7] = nums[nums[9]] = 8 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 We'll move to index 7, since we found 7 at nums[9].

10 of 11

Created with Fabric.js 3.6.6 We found cycle in nums array.nums[0] = 2nums[2] = nums[nums[0]] = 8nums[8] = nums[nums[2]] = 1nums[1] = nums[nums[8]] = 5nums[5] = nums[nums[1]] = 3nums[3] = nums[nums[5]] = 6nums[6] = nums[nums[3]] = 9nums[9] = nums[nums[6]] = 7nums[7] = nums[nums[9]] = 8 indexes 0 1 2 3 4 5 6 7 8 9 nums 2 5 8 6 8 3 9 8 1 7 After traversing in nums, we can see that there is a cycle that starts at nums[8] and returns to nums[8].

11 of 11

As seen above, we’ve found that there is a cycle in an array with a duplicate number. Now, the problem is to find the entry point of the cycle, which will be our duplicate number.

We solve this problem in two parts using the slow and fast pointers.

In the first part, the slow pointer moves once, while the fast pointer moves twice as fast as the slow pointer until both of the pointers meet each other. Since the fast pointer is moving twice as fast as the slow pointer, it will be the first one to enter and move around the cycle. At some point after the slow pointer also enters and moves in the cycle, the fast pointer will meet the slow pointer. This will be the intersection point.

Note: The intersection point of the two pointers is, in the general case, not the entry point of the cycle.

Let’s look at a visual representation of the first part of our solution:

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 This graph shows the graphical presentation of array.

1 of 9

Created with Fabric.js 3.6.6 slow & fast 2 8 1 5 3 6 9 7 slow fast We have two pointers, slow and fast. We'll present slow with the blue color and fast with the purple color and if both slow and fast pointers points the same node, we'll present it using red color.

2 of 9

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 The slow pointer is pointing to 8 and the fast pointer is pointing to 1.

3 of 9

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 The slow pointer is pointing to 1 and the fast pointer is pointing to 3.

4 of 9

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 The slow pointer is pointing to 5 and the fast pointer is pointing to 9.

5 of 9

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 The slow pointer is pointing to 3 and the fast pointer is pointing to 8.

6 of 9

Created with Fabric.js 3.6.6 The slow pointer is pointing to 6 and the fast pointer is pointing to 5. 2 8 1 5 3 6 9 7

7 of 9

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 The slow pointer is pointing to 9 and the fast pointer is pointing to 6.

8 of 9

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 Both the slow and the fast pointer points to 7. Wehave found the intersection point, that is 7. So, the first part of the solution ends here.

9 of 9

In part two, we’ll start moving again in the cycle, but this time, we’ll slow down the fast pointer so that it moves with the same speed as the slow pointer.

Let’s look at the journeys of the two pointers in part two:

  • The slow pointer will start from the 0th0^{th} position.

  • The fast pointer will start from the intersection point.

  • After a certain number of steps, let’s call it FF, the slow pointer meets the fast pointer. This is the ending point for both pointers.

  • This common ending position will be the entry point of the cycle.

Let’s look at the visual presentation of the second part of our solution:

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 We have found the intersection point, that is 7. So, the first part of the solution ends here. Now, we'll move to the second part of the solution.

1 of 3

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 Now, the starting point of the fast pointer will be the intersection point.The slow pointer will start from the start of the array.Both pointers will take move at the same speed.

2 of 3

Created with Fabric.js 3.6.6 2 8 1 5 3 6 9 7 After taking 1 step each, the fast and the slow pointers will both point to 8. We have found the entry point of the cycle,which is also the duplicate number in the array.

3 of 3

Now, let’s try to understand how it is that our solution is able to always locate the entry point of the cycle.

Let’s return to the example we just discussed, using this graphical representation:

A graphical presentation of the array
  • 77 is the intersection point where the slow and fast pointers will meet.

  • 88 is the entry point of the cycle, which is our duplicate number.

The fast pointer is traversing two times faster than the slow pointer. This can be represented by the following equation:

dfast=2dslowd _{fast} = 2d_{slow} ——— (1)(1)

Here, dd represents the number of elements traversed.

Let’s look at the following diagram to see the steps taken by the slow and fast pointers from the starting point to the intersection point:

A list with a cycle

In the diagram above:

  • Green represents the entry point of the cycle.

  • Blue represents the intersection point.

  • Yellow represents the starting point.

  • FF represents the steps taken from the starting point to the entry point.

  • aa represents the steps taken to reach the intersection point from the entry point.

  • CC represents the cycle length, in terms of the number of steps taken to go once around the cycle.

With this setup in mind, let’s see the distance traveled by the slow and fast pointers.

The slow pointer travels FF steps from the starting point to the entry point of the cycle and then takes aa steps from the entry point to the intersection point of the cycle, that is, the point where both pointers intersect. So, we can express the distance traveled by the slow pointer in the form of this equation:

dslow=F+a d _{slow} = F + a\space——— (2)\space(2)

In the time it takes the slow pointer to travel F+aF+a steps, the fast pointer, since it’s traveling twice as fast as the slow pointer, will have also traveled around the cycle at least once. So, we can say the fast pointer, first, travels FF steps from the starting point to the entry point of the cycle, then travels at least a cycle, and at the end travels aa steps from the entry point to the intersection point of the cycle. Now, we can express the distance traveled by the fast pointer as the following equation:

dfast=F+C+a d _{fast} = F + C + a\space——— (3)\space(3)

Recall eq. (1):(1):

dfast=2dslowd _{fast} = 2d_{slow} ——— (1)(1)

If we substitute the equivalent expression of dslowd_{slow} given in eq. (2)(2) and the equivalent expression of dfastd_{fast} given in eq. (3)(3) into eq. (1)(1), we get:

F+C+a=2(F+a)F+C+a = 2(F+a)

Let’s simplify this equation:

F+C+a=2F+2aF+C+a = 2F+2a

C=F+aC = F+a

Therefore, the distance from the starting point to the intersection point, F+aF+a, equals CC.

We can also re-arrange this equality as follows:

F=CaF=C-a

Let’s consult our diagram again:

A list with a cycle

As we can see, CaC-a is, in fact, the distance from the intersection point back to the entry point. This illustrates why, when we move one pointer forward, starting at the intersection point, and another pointer from the starting point, the point where they meet is the entry point of the cycle.

Note: The proof above does not consider the case where FF is longer than the length of the cycle. In this situation, it’s possible that the fast pointer will go around the cycle more than once. To express this more general case, we can say that the distance covered by the fast pointer from the entry point to the intersection point is: F+nC+aF + nC + a, where nn is a positive integer. As a result, our substitution will take this form: F+nC+a=2(F+a)F + nC + a = 2(F+a), which simplifies to nC=F+anC = F + a, that is: F=nCaF = nC - a. This simply means that after going around the cycle nn times, the fast pointer will still be aa steps behind the entry point of the cycle.

Let’s look at the implementation of the solution discussed above:

Find The Duplicate Number

Time complexity#

The time complexity of the algorithm is O(n)O(n), where nn is the length of nums. This is because, in each part of the solution, the slow pointer traverses nums just once.

Space complexity#

The algorithm takes O(1)O(1) space complexity, since we only used constant space to store the fast and slow pointers.

Find The Duplicate Number

Palindrome Linked List